package leetcode.linked;

import java.util.*;

/**
 * 82. 删除排序链表中的重复元素 II
 * <p>
 * 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
 * <p>
 * 示例 1:
 * <p>
 * 输入: 1->2->3->3->4->4->5
 * 输出: 1->2->5
 * <p>
 * 示例 2:
 * <p>
 * 输入: 1->1->1->2->3
 * 输出: 2->3
 * <p>
 * 分析：记录元素频率，在不改变元素相对位置情况下，需要借助原来head进行遍历然后将频率为1的接到新的链表上
 * 时间复杂度：O(n)  空间复杂度 开辟存放n个元素链表的map 和一个新的list 最差情况下为O(n^2)
 */
public class Solution82 {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return null;
        }
        //设立虚拟头结点
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        Map<Integer, Integer> map = new HashMap<>();
        ListNode cur = dummyHead.next;
        while (cur != null) {
            int num = cur.val;
            if (!map.containsKey(num)) {
                map.put(num, 1);
            } else {
                map.put(num, map.get(num) + 1);
            }
            cur = cur.next;
        }
        //重新赋值
        cur = dummyHead.next;

        //创建一个新的链表
        ListNode newDummyHead = new ListNode(-1);
        ListNode newHead = newDummyHead;
        while (cur != null) {
            int key = cur.val;
            Integer value = map.get(key);
            if (value == 1) {
                ListNode node = new ListNode(key);
                newHead.next = node;
                newHead = newHead.next;
            }
            cur = cur.next;
        }

        return newDummyHead.next;
    }
}
